package KMP算法;

public class KMP算法 {

	public static void main(String[] args) {
		
		String str1 = "BBC ABCDAB ABCDABCDABDE";
		String str2 = "ABCDABD";
		
		int[] next  = kmpNext(str2);
		int index = kmpSearch(str1, str2, next);
		System.out.println(index);
	}
	
	/**
	 * kmp算法
	 * @param str1 源字符串
	 * @param str2 子串
	 * @param next 部分匹配串，子串部分匹配表
	 */
	public static int kmpSearch(String str1, String str2, int[] next) {
		
		//遍历
		for(int i = 0, j = 0; i < str1.length(); i++) {
			
			//如果i j不同，调整j的大小，左右，直接跳回到最近相同的字符上，不用一个一个暴力对比
			while(j > 0 && str1.charAt(i) != str2.charAt(j)) {
				j = next[j - 1];
			}
			
			if(str1.charAt(i) == str2.charAt(j)) {
				j++;
			}
			
			if(j == str2.length()) {
				//+1是因为for中只有i++，所以i++以及后，j在if中++，所以j 比 i 大1
				return i- j + 1;
			}
		}
		
		return -1;
	}
	
	
	/**
	 * next函数，表示子串部分匹配值表，有了表就不用一个一个暴力对比，可以跳过不需要的字符
	 * 	原理：部分匹配表就是 前缀 和 后缀 的最长公共元素，例如字符串ABCAB
	 * 		A: 前缀后缀空 							0
	 * 		AB:A ;	B								0
	 * 		ABC:A,AB ; B,BC							0
	 * 		ABCA:A,AB,ABC ; BCA,CA,A				1
	 * 		ABCAB:A,AB,ABC,ABCA ; BCAB,CAB,AB,A		2
	 * 	表：0,0,0,1,2
	 * @param dest
	 * @return
	 */
	public static int[] kmpNext(String dest) {
		
		//定义一个next数组保存匹配值
		int[] next = new int[dest.length()];
		
		//字符串长度为1时，前后缀空，所以匹配值是0
		next[0] = 0;
		//遍历，得到最长匹配表
		for(int i = 1, j = 0; i < dest.length(); i++) {
			
			//注意理解！！！
			//i是子串，j是最长匹配串，i串在上，j串在下，i = 1；j = 0，i代表前缀，j代表后缀
			// i A B C A B
			// 	   |	
			// j A B C A B
			//   |
			//i先走，对比j，如果相同，i++,j++
			//如果不相同(while)，从i位置开始，j开始一直向前回溯，重新找到与i相同的值，再次开始
			while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
				j = next[j-1];
			}
			
			//当i与j形同时，继续向后对比
			if(dest.charAt(i) == dest.charAt(j)) {
				//j在此处加1，只有相同时才能向后继续找，不同时向前找
				j++;
			}
			
			//在j停下来的位置上表示相同字符串个数
			next[i] = j;
		}
		return next;
	}
	
	/**
	 * BF暴力匹配算法
	 * @param str1
	 * @param str2
	 * @return
	 */
	public static int bfSearch(String str1, String str2) {
		//两字符串转数组
		char[] arr1 = str1.toCharArray();
		char[] arr2 = str2.toCharArray();
		//开始匹配位置
		int i = 0;
		int j = 0;
		
		while(i < arr1.length && j < arr2.length) {
			//开始匹配
			if(arr1[i] == arr2[j]) {
				i++;
				j++;
			}else {
				//退回上一次开始的下一个位置
				i = i - (j - 1);//i = i - j + 1;
				//子串归零，重新开始
				j = 0;
			}
		}
		
		//结束条件，子串全部匹配完成
		if(j == arr2.length) {
			//子串开始位置
			return i - j;
		}
		return -1;
	}
}
